package com.hy.day;

import java.util.HashMap;
import java.util.Map;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:1542. 找出最长的超赞子字符串
 *
 * 给你一个字符串 s 。请返回 s 中最长的 超赞子字符串 的长度。
 * 「超赞子字符串」需满足满足下述两个条件：
 * 该字符串是 s 的一个非空子字符串
 * 进行任意次数的字符交换后，该字符串可以变成一个回文字符串
 *
 * User:Mr.Du
 * Date:2024/5/20
 * Time:9:54
 */
public class LongestAwesome {

    /**
     * 计算给定字符串中最长的超赞的子串长度。
     * 一个字符串令人敬畏当且仅当它包含每个数字恰好一次，且相邻数字的二进制异或值不为0。
     *
     * @param s 输入的字符串
     * @return 返回最长的超赞的子串的长度
     */
    public int longestAwesome(String s) {
        // 初始化状态映射，存储当前异或值到其索引的映射，并预处理初始状态
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int n = s.length(), cur = 0, res = 0; // n为字符串长度，cur为当前异或值，res为最长子串长度

        // 遍历字符串更新当前异或值，并查找之前的异或值以计算子串长度
        for(int i = 0; i < n; ++i){
            int x = s.charAt(i) - '0'; // 获取当前字符对应的数字
            cur = (1 << x) ^ cur; // 更新当前异或值
            if(map.containsKey(cur)) // 如果当前异或值已经出现过，则更新最长子串长度
                res = Math.max(res, i - map.get(cur));
            else map.put(cur, i); // 如果当前异或值未出现过，则记录其索引

            // 遍历所有可能的数字，计算与当前异或值异或后的值，查找之前的出现位置，更新最长子串长度
            for(int j = 0; j < 10; ++j){
                int find = (1 << j) ^ cur;
                if(map.containsKey(find)) res = Math.max(res, i - map.get(find));
            }
        }
        return res; // 返回最长子串长度
    }
}
